This invention relates to improved methods and apparatus for providing mix networks.
A mix network is a privacy primitive used to reorder a list of inputs, thereby producing a list of outputs, so that the items of the output correspond to the items of the inputs, but in a way that the relative order cannot be determined. There are essentially three types of mix networks: (1) Those in which the receiver of the output needs to trust that the output is of the right form (i.e. corresponds to the input); (2) Those in which the receiver needs to trust that one of the servers producing the output is honestxe2x80x94if that is so, then the output must be correct; and (3) Those in which the receiver can verify the correctness of the output, and does not need to trust anybody. Schemes of the first type are not very useful. Schemes of the second type are useful for most applications, and there exist efficient solutions for these, especially when the input sizes are large. For certain applications a scheme of the third type is preferred. There may be some recent proposals of how to do schemes of the third type. However, these recently proposed schemes are not as efficient as the methods disclosed in the present application. In addition, the applicant claims priority over some of the other most recently proposed methods and these may or may not be prior art. For the most part these proposed methods do not handle small inputs
Generally, a mix network takes a collection of n encrypted input data messages (each message including a plurality of data bits or data signals), re-encrypts them, and outputs them in an unrevealed, randomly permuted order. The original conception of mix networks is by Chaum. They have been used or proposed for use for anonymous e-mail, Web browsing, and secure elections, as well as for seemingly unrelated applications such as anonymous payments systems and secure multi-party computation.
In recent years threshold mix networks have been proposed which employ multiple mix servers where the correctness and privacy of the mix is robust against malicious coalitions of mix servers. However, most prior art multiple mix server techniques are inefficient, often requiring between fifty up to more than a thousand exponentiation operations. One prior art mix network proposed by Jakobsson brought the number of exponentiations down to one per input item (each item is a single message comprised of multiple data bits or data signals) but this prior art mix network assumed very large input batches (of about 1 million items).
The present invention provides the first highly efficient mix network for small numbers of inputs. Four data messages (each message comprised of multiple data bits or signals) would be a typical number of inputs. The solution, which is based on techniques used to sort data (but which in embodiments of the present invention are used to unsort data) allows a receiver to verify the correctness of the output.
The present invention uses the structure of sorting/permutation networks to permute the input. This is done in a way that changes the position of pairs of items (iteratively or in parallel), which allows efficient proofs to be employed for proving correctness (it is known that proofs become significantly more expensive as they become bigger, and in embodiment of the present invention, we break down the proofs in their smallest components, i.e., to prove statements about pairs of items instead of vectors). We develop novel methods relating to signature schemes to realize these proofs.
Embodiments of the present invention provide a mix network method and apparatus which is highly efficient on small input batches and is robust and private in the face of collusion by any minority set of mix servers. Additionally, the mix network method and apparatus has the feature of being publicly verifiable because the mixing method yields a transcript of results that can demonstrate to a third party that the mix proceeded correctly.
In one embodiment of the present invention an apparatus comprised of a plurality of mix servers is provided. Each mix server includes a randomizer network. Each randomizer network receives a plurality of input data messages and performs re-encryption and permutation operations on the plurality of input data messages to form a plurality of output data messages. The randomizer networks of the plurality of mix servers are arranged in a chain so that the first randomizer network of the first mix server in the chain receives its plurality of input data messages and provides its plurality of output data messages to the next randomizer network of the following mix server in the chain. Each randomizer network is comprised of a plurality of randomizers, wherein each randomizer receives first and second input data messages and produces first and second output data messages, wherein the first output data message is a re-encryption of either the first or the second input data message and the second output data message is a re-encryption of the other input data message. The apparatus may be further comprised of a bulletin board having computer memory. Each mix server produces proof to the bulletin board that each randomizer of each randomizer network has re-encrypted and permuted in a proper manner.
The re-encryption step may be replaced by decryption at one or more steps.